2018 计蒜之道 初赛 第四场

贝壳找房均价计算

• 思路：主要就是判断是否有4，然后使用long long的类型，否则会溢出。

• 代码

  #include <cstdlib>
  #include <string>
  #include <iostream>
  #include <fstream>
  #include <vector>
  #include <sstream>
  #include <unordered_map>
  #include <algorithm>
  #include <map>
  #include <set>
  #include <unordered_set>
  #include <stdio.h>
  #include <string.h>
  #include <numeric>
  
  using namespace std;
  typedef long long ll;
  
  //字符串分割函数
  std::vector<std::string> split(const std::string &str, const std::string &pattern)
  {
      std::string::size_type pos;
      std::vector<std::string> result;
      int size = str.size();
  
      for (int i = 0; i<size; i++)
      {
          pos = str.find(pattern, i);
          if (pos != -1 )
          {
              result.push_back(str.substr(i, pos - i));
              i = pos + pattern.size() - 1;
          }
          else
          {
              result.push_back(str.substr(i));
              break;
          }
      }
      return result;
  }
  
  int main()
  {
      int T = 0;
      scanf("%d\n", &T);
      for (int t = 0; t < T; t++)
      {
          char chs[2000] = {0};
          gets( chs );
          string str( chs );
          vector<string> sstrs = split( chs, "." );
          ll ret = stoll(sstrs[0]);
          for (int i = 0; i < sstrs[1].size(); i++)
          {
              if ( sstrs[1][i] <= '3')
                  break;
              else if (sstrs[1][i] >= '5')
              {
                  ret++;
                  break;
              }
          }
          printf("%lld\n", ret);
      }
  
      return 0;
  }
  

贝壳找房搜房（简单）

• 思路：我之前的想法是将任意两个房源数组合并，直到无法合并为止，再生成对应的列表，但是没有实现，最后实现了一个暴力穷举的方法，但是这种方法是超时的。

• 超时的暴力穷举代码

  #include <cstdlib>
  #include <string>
  #include <iostream>
  #include <fstream>
  #include <vector>
  #include <sstream>
  #include <unordered_map>
  #include <algorithm>
  #include <map>
  #include <set>
  #include <unordered_set>
  #include <stdio.h>
  #include <string.h>
  #include <numeric>
  
  using namespace std;
  typedef long long ll;
  
  bool repeated( int num, int n )
  {
      vector<int> nums( n+1, 0 );
      while (num != 0)
      {
          int tmp = num % 10;
          if (tmp > n || tmp == 0 || nums[tmp] != 0)
              return true;
          nums[tmp] = 1;
          num = num / 10;
      }
      return false;
  }
  
  bool right(const vector<int>& result, const vector<vector<int>>& nums)
  {
      for (int i = 0; i < nums.size(); i++)
      {
          for (int j = 0; j < nums[i].size(); j++)
          {
              for (int k = 0; k < result.size(); k++)
              {
                  if (result[k] == nums[i][j])
                  {
                      j++;
                      k++;
                      while (k < result.size() && j < nums[i].size() && nums[i][j] == result[k])
                      {
                          j++;
                          k++;
                      }
                      if (j < nums[i].size())
                          return false;
                      else
                          break;
                  }
              }
          }
      }
      return true;
  }
  
  int main()
  {
      int n = 0, m = 0;
      scanf("%d %d", &n, &m);
      vector<vector<int>> nums( m );
      map<int, int> maps;
      int tmp = 0;
      for (int i = 0; i < m; i++)
      {
          scanf("%d", &tmp);
          nums[i] = vector<int>( tmp, 0 );
          for (int j = 0; j < tmp; j++)
          {
              scanf("%d", &nums[i][j]);
              ++maps[nums[i][j]];
          }
      }
  
      int cnt = 1;
      for (int i = 0; i < n; i++)
          cnt *= 10;
  
      bool succeed = false;
      for (int i = cnt / 10; i < cnt; i++)
      {
          if (repeated(i, n))
              continue;
  
          vector<int> result( n, 0 );
          tmp = i;
          int index = 0;
          while (tmp != 0)
          {
              result[index++] = tmp % 10;
              tmp /= 10;
          }
          std::reverse( result.begin(), result.end() );
  
          if (right(result, nums))
          {
              for (int j = 0; j < n - 1; j++)
                  printf("%d ", result[j]);
              printf("%d\n", result.back());
              succeed = true;
              break;
          }
  
      }
  
      if (!succeed)
          printf("-1\n");
  
      return 0;
  }